package LeetCodeHot100;

import java.util.HashSet;
import java.util.Set;

/**
 * 128. 最长连续序列
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 思路： 最长，往往能想到动态规划，其实就可以使用动态规划来解决此问题， 但问题是题目要求是可在原数组中不连续
        所以 动态规划用起来不容易
    所以还是使用一个hash表来统计长度。 可以使用一个Set去重， 然后遍历去重set统计长度。
    这道题的核心点在于，它是不安元素顺序来最长的，而是统计出现过可以排列为从小到大的元素去统计，而且必须连续。
 */

public class LeetCode128 {

    public int longestConsecutive(int[] nums) {
        // 先去重操作
        Set<Integer> set = new HashSet<>();
        for (int num: nums) {
            set.add(num);
        }
        // 然后排列
        int res = 0;
        for (int num: set) {
            int cur = num;
            // 从set中的当前元素开始，如果集合中没有比cur更小的元素，就可以去以它为起点连续数字的统计
            if(!set.contains(cur-1)){
                while (set.contains(cur+1)){
                    cur++;
                }
            }
            res = Math.max(res,cur-num+1);
        }
        return res;
    }

}
